Мировой финансовый кризис –
довольно серьезная тема. Некоторые люди бывают расслаблеными, а другие весьма
обеспокоенными. Джон – один из них. Его очень беспокоит изменение состояния
фондовой биржи. Он ежедневно следит за ценами на акции в поисках тенденций к
росту. Для данной последовательности чисел p1, p2, ..., pn, представляющих цены на акции, восходящий тренд
является подпоследовательностью pi1 < pi2 < ... < pik с i1 < i2 < ... < ik. Задача Джона –
найти самый длинный восходящий тренд.
Вход. Каждый набор данных
соответствует определенному набору курсов акций. Набор данных начинается с
длины l (l ≤
105) последовательности чисел,
за которыми следуют целые числа.
В любых местах входных
данных могут встречаться пробелы. Входные данные верны и заканчиваются концом
файла.
Выход. Выведите длину
самого длинного восходящего тренда. Для каждого набора данных выведите ответ с
новой строки.
|
Пример входа |
Пример выхода |
|
6
5
2 1 4 5 3 3 1
1 1 4
4
3 2 1 |
3 1 1 |
наибольшая возрастающая
подпоследовательность
Состоит
из нескольких тестов. Каждый тест содержит последовательность чисел, для
которой следует найти длину наибольшей возрастающей подпоследовательности.
Реализация алгоритма
Объявим вспомогательный массив lis.
#define MAX 100001
int lis[MAX];
Основная
часть программы. Читаем и обрабатываем входную последовательность.
while (scanf("%d",&n) == 1)
{
for (len = i = 0; i < n; i++)
{
scanf("%d",&element);
pos =
lower_bound(lis,lis+len,element) - lis;
if (pos < len) lis[pos] = element; else lis[len++] = element;
}
Выводим
длину НВП.
printf("%d\n",len);
}
Java реализация
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner con = new
Scanner(System.in);
int lis[] = new int[100001];
while (con.hasNextInt())
{
int n = con.nextInt();
int len = 0;
for (int i = 0; i < n; i++)
{
int element = con.nextInt();
int pos = Arrays.binarySearch(lis, 0, len, element);
if(pos < 0) pos = - (pos + 1);
lis[pos] = element;
if(pos == len) len++;
}
System.out.println(len);
}
con.close();
}
}